In a typical super-resolution application case, an input video sequence is given, from which several downscaled versions of the same video sequence can be computed. Alternatively, other images or video sequences may be used. Some known algorithms for performing super-resolution split the input image or video into patches and operate patch by patch. One known technique is based on image self-similarity, i.e. similar patches are searched in different downscaled versions of an image. It can be based on Approximate Nearest-Neighbor Fields (ANNF). The purpose of an ANNF is to locate for each patch of a source image or video, e.g. an input video, the k most similar patches out of all the available patches in a target image or video, e.g. spatio-temporally downscaled versions of the source image or video. All these patches have same size. Thus, an ANNF defines for each source patch one or more target patches.
“PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing”, Barnes, C. et al., ACM Trans. on Graphics, vol. 28(3), 2009 [1] describes an iterative image editing approach for quickly finding Approximate Nearest Neighbor (ANN) matches between image patches. It is a fast algorithm for ANNF computation called PatchMatch, which relies on the iterative application of two stages: first, a random search is made with exponentially shrinking search windows, assuming an exponential distribution for the distance to the nearest neighbor. The second step is a propagation of the best locations from spatially neighboring patches, assuming high coherency for the spatial distribution of nearest neighbors.
“The Generalized PatchMatch Correspondence Algorithm”, Barnes, C. et al., ECCV 2010 [2] extends the PatchMatch core idea to consider, apart from location, also scale and rotation as new search dimensions for 2D image patches. Further, acceleration techniques are described, including a search strategy that is called “enrichment” and that generalizes coherent or locally similar matches from spatial neighborhoods to neighborhoods in nearest neighbor space. A large performance gain can be achieved by considering Forward Enrichment if the search is done in exactly the same image and scale as the input. This reduces its applicability to only denoising problems.
US2013/163884 discloses enrichment of patch mapping by considering an initial patch's nearest neighbors and their respective nearest neighbors. The enrichment can be of a “forward” type or of an “inverse” type.
Unless mentioned otherwise, the term nearest neighbors as used herein refers to nearest neighbors in the patch space: for a given patch, nearest neighbors in the patch space are patches that are most similar to the given patch, as opposed to spatially nearest neighbors which are spatially adjacent to the given patch but not necessarily similar. A nearest-neighbor field (NNF) can be understood as a function f:A−>R2 that is defined over all possible patch coordinates (locations of patch centers) in an image A. Given a patch coordinate a in image A and its corresponding nearest neighbor b in image B, the NNF is f(a)=b. Enrichment is defined as the propagation of good matches from a patch to its k nearest neighbors (k-NN), or vice versa. It improves a given NNF by considering a “richer” set of potentially good candidate matches than propagation or random search alone. In other words, propagation can be viewed as moving good matches along a rectangular lattice whose nodes are patch centers (pixels), whereas enrichment moves good matches along a graph where every node is connected to its k-NN. Forward enrichment uses compositions of the function f with itself to produce candidates for improving the nearest neighbor field (i.e. f2). If f is a NNF with k neighbors, the NNF f2 is constructed by looking at all k2 of the nearest neighbors nearest neighbors. Different from Forward enrichment, inverse enrichment walks the nearest-neighbor pointers backwards to produce candidates for improving the NNF. Inverse enrichment computes the inverse f−1 of the function f. The inverse f−1(a) may have zero values if no patches point to a patch, or multiple values if multiple patches point to a patch. A problem that remains to be solved is how to enhance the performance of ANNF based searches.